The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(O(1), O(n^1)).

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

t(o(x1)) → m(a(x1))
t(e(x1)) → n(s(x1))
a(l(x1)) → a(t(x1))
o(m(a(x1))) → t(e(n(x1)))
s(a(x1)) → l(a(t(o(m(a(t(e(x1))))))))
n(s(x1)) → a(l(a(t(x1))))

Rewrite Strategy: INNERMOST

(1) CpxTrsMatchBoundsProof (EQUIVALENT transformation)

A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 3.
The certificate found is represented by the following graph.

Start state: 1136
Accept states: [1137, 1138, 1139, 1140, 1141]
Transitions:
1136→1137[t_1|0]
1136→1138[a_1|0]
1136→1139[o_1|0]
1136→1140[s_1|0]
1136→1141[n_1|0]
1136→1136[m_1|0, e_1|0, l_1|0]
1136→1142[s_1|1]
1136→1143[t_1|1]
1136→1144[t_1|2]
1142→1137[n_1|1]
1142→1143[n_1|1]
1142→1144[n_1|1]
1143→1138[a_1|1]
1144→1145[a_1|2]
1145→1146[l_1|2]
1145→1147[t_1|3]
1146→1137[a_1|2]
1146→1143[a_1|2]
1146→1144[a_1|2]
1147→1137[a_1|3]
1147→1143[a_1|3]
1147→1144[a_1|3]

(2) BOUNDS(O(1), O(n^1))